<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    
    <script>
        // 时间复杂度是O(n) 字符的长度 map查找的是复杂度是O(1) 结果就是 O(n) + O(1) 就是 O(n)
        // 空间复杂度也是 O(n) map结构的大小
        // 1. 利用js的map结构 
        // 1.1 先遍历s 如果有值，就给map里面创建一个
        // 1.2 再遍历t 如果有值 就减一
        // 1.3 如果最终的map结构，里面的属性，有<0的，就给return false
        // 1.4 如果都是0，就return true
        var isAnagram = function(s, t) {
            let map = new Map() 
            // 比较两个字符串的长度是否相等的空间复杂度是O(n)
            if(s.length !== t.length) {
                return false
            }
            // 遍历s字符串 时间O(n)
            for(let i of s) {
                if(map.has(i)) {
                    map.set(i, map.get(i) + 1)
                } else {
                    map.set(i, 1)
                }
            }   
            // 遍历t字符串 时间O(n)
            for(let i of t) {
                // 首先判断 map里面有这个i属性，其次有加判断条件 map.get(i) > 0 后者直接限制 小于0的清空
                if(map.has(i) && map.get(i) > 0) {
                    map.set(i, map.get(i) - 1)
                } else {
                    return false
                }
            }

            // 下面写法 map遍历有问题 map如何进行遍历? 易错点 注意
            // for(let i in map) {
            //     if (map[i] !== 0) {
            //         return false
            //     }
            // }
            return true
        };
        // console.log(isAnagram('abc', 'acd'));
        // console.log(isAnagram('anagram', 'nagaram')); // 这个测试用例未能通过
        console.log(isAnagram('aacc', 'ccac')); // 这个测试用例未能通过


        // 2. 法二 排序后 如果长度一致，就相等
        // 记得先排序 排序后要再转化位字符串
        // 时间复杂度O(nlogn) - 排序;比较长度 O(n) O(nlogn + n) => O(nlogn)
        // 空间复杂度为 O(n) n就是字符a或者b的长度
        var isAnagram2 = function(s, t) {
            let a = [...s].sort().join('')
            let b = [...t].sort().join('')
            if(s.length === t.length && a === b) {
                console.log(a);
                console.log(b);
                return true
            }
            return false
            // return s.length === t.length && [...s].sort() === [...t].sort()
        }
        console.log(isAnagram2('aacc', 'ccac'));
        console.log(isAnagram2('aabb', 'bbaa'));

        
        // 3.
        // 时间复杂度为 O(n) n 为遍历的字符的长度
        // 空间复杂度为 O(s) s 这里为26 就是数组的长度
        // ASCLL和Unicode码的区别是什么
        const isAnagram3 = (s, t) => {
            if(s.length !== t.length) {
                return false
            } 
            let table = new Array(26).fill(null)
            // 这里用 codePointAt 和 charCodeAt 都可以 因为只是针对字符 如果是unicode用codePointAt
            const base = 'a'.charCodeAt(0)
            for(let i = 0; i < s.length; i++) {
                table[s.codePointAt(i) - base]++
            }
            for(let i = 0; i < t.length; i++) {
                table[t.codePointAt(i) - base]--
                if (table[t.codePointAt(i)] - base < 0){
                    return false
                }
            }
            return true
        }
        console.log(isAnagram3('aacc', 'ccac'));
        console.log(isAnagram3('aabb', 'bbaa'));
    </script>
</body>
</html>